/* 二叉树相关操作:
二叉树先序遍历
二叉树中序遍历
二叉树后序遍历
求二叉树的深度
求二叉树的叶子节点个数
求二叉树的分支节点个数
求二叉树的单分支节点个数
求二叉树的双分支节点个数
先序遍历二叉树的序列化
先序遍历二叉树反序列化
层序遍历序列化
层序遍历反序列化
获取到某节点的路径
反转二叉树
判断t1树是否包含t2树全部的拓扑结构
判断二叉树是否为平衡二叉树
判断二叉树是否为完全二叉树
通过有序数组生成平衡搜索二叉树
找到两个节点的最近公共祖先
求二叉树节点间的最大距离
求二叉树第K层的节点个数
Morris遍历二叉树
 */
 
 
public class Node{
	public int value;
	public Node left;
	public Node right;
	
	public Node(int data){
		this.value = data;
	}
}
 
//二叉树先序遍历
public void preOrderRcur(Node head){
	if(head==null){
		return;
	}
	System.out.print(head.value+" ");
	preOrderRcur(head.left);
	preOrderRcur(head.right);
 }
 
//二叉树中序遍历
public void inOrderRecur(Node head){
	if(head==null){
		return;
	}
	inOrderRecur(head.left);
	System.out.print(head.value +" ");
	inOrderRecur(head.right);
}

//二叉树后序遍历
public void posOrderRecur(Node head){
	if(head==null){
		return;
	}
	posOrderRecur(head.left);
	posOrderRecur(head.right);
	System.out.print(head.value + " ");
}

//求二叉树的深度
public int treeDeep(Node head){
	if(head==null){
		return 0;
	}
	int nLeft = treeDeep(head.left);
	int nRight = treeDeep(head.right);
	return (nLeft>nRight)?(nLeft+1):(nRight+1);
}

//求二叉树的叶子节点个数
public int leaf_num(Node head){
	if(head==null){
		return 0;
	}
	if(head.left==null && head.right==null){
		return 1;
	}
	else{
		return(leaf_num(head.left)+leaf_num(head.right));
	}
}

//求二叉树的分支节点个数
public int branch_num(Node head){
	if(head==null){
		return 0;
	}
	if(head.left!=null || head.right!=null){
		return(branch_num(head.left)+branch_num(head.right)+1);
	}
	else{
		return(branch_num(head.left)+branch_num(head.right));
	}
}

//求二叉树的单分支节点个数
public int single_branch_num(Node head){
	if(head==null){
		return 0;
	}
	if(head.left!=null&&head.right==null || head.left==null&&head.right!=null){
		return(branch_num(head.left)+branch_num(head.right)+1);
	}
	else{
		return(branch_num(head.left)+branch_num(head.right));
	}
}
 
//求二叉树的双分支节点个数
public int single_branch_num(Node head){
	if(head==null){
		return 0;
	}
	if(head.left!=null&&head.right!=null){
		return(branch_num(head.left)+branch_num(head.right)+1);
	}
	else{
		return(branch_num(head.left)+branch_num(head.right));
	}
}

//先序遍历二叉树的序列化
public String serialByPre(Node head){
	if(head==null){
		return "#!";
	}
	String res = head.value + "!";
	res +=serialByPre(head.left);
	res +=serialByPre(head.right);
	return res;
}

//先序遍历二叉树反序列化
public Node reconByPreSting(String preStr){
	String[] values = preStr.split("!");
	Queue<String> queue = new LinkedList<String>();
	for(i=0;i<values.length;i++){
		queue.offer(values[i]);
	}
	return reconPreOrder(queue);
}

public Node reconPreOrder(Queue<String> queue){
	String value = queue.poll();
	if(value.equals("#")){
		return null;
	}
	Node head = new Node(Integer.valueOf(value));
	head.left = reconPreOrder(queue);
	head.right = reconPreOrder(queue);
	return head;
}

//层序遍历序列化
public String serialByLevel(Node head){
	if(head==null){
		return "#!";
	}
	String res = head.value +"!";
	Queue<Node> queue = new LinkedList<Node>();
	queue.offer(head);
	while(!queue.isEmpty()){
		head = queue.poll();
		if(head.left !=null){
			res += head.left.value+"!";
			queue.offer(head.left);
		}
		else{
			res += “#!”;
		}
		if(head.right != null){
			res += head.right.value+"!";
			queue.offer(head.right);
		}
		else{
			res += “#!”;
		}
	}
	return res;
}

//层序遍历反序列化
public Node reconByLevelString(String levelStr){
	String[] values = levelStr.split("!");
	int index = 0;
	Node head = generateNodeByString(values[index++]);
	Queue<Node> queue = new LinkedList<Node>();
	if(head !=null){
		queue.offer(head);
	}
	Node node = null;
	while(!=queue.isEmpty()){
		node =queue.poll();
		node.left = generateNodeByString(value[index++]);
		node.right = generateNodeByString(value[index++]);
		if(node.left!=null){
			queue.offer(node.left);
		}
		if(node.right!=null){
			queue.offer(node.right);
		}
	}
	return head;
} 

//获取到某节点的路径
public boolean getPathFromRoot(Node root,Node node,ArrayList<integer> pathArray){
	if(root==null||node==null){
		return false;
	}
	pathArray.add(root.value);
	if(root.value==node.value){
		return true;
	}
	if(root.left!=null){
		if(getPathFromRoot(root.left,node,pathArray)){
			return true;
		}
	}
	if(root.right!=null){
		if(getPathFromRoot(root.right,node,pathArray)){
			return true;
		}
	}
	//回溯
	pathArray.remove(pathArray.size()-1);
	return false;
}

//反转二叉树
public Node inverTree(Node root){
	if(root!=null){
		Node left = inverTree(root.left);
		Node right = inverTree(root.right);
		root.right = left;
		root.left = right;
		return root;
	}
	return null;
}

//判断t1树是否包含t2树全部的拓扑结构
pubulic boolean contains(Node t1, Node t2){
	return check(t1,t2)||contains(t1.left,t2)||contains(t1.right,t2);
}
public boolean check(Node h,Node t2){
	if(t2==null){
		return true;
	}
	if(h==null||h.value!=t2.value){
		return false;
	}
	return check(h.left,t2.left)&&check(h.right,t2.right);
}
 
//判断二叉树是否为平衡二叉树
public boolean isBalance(Node head){
	boolean[] res = new boolean[1];
	res[0] = true;
	getHeight(head,1,res);
	return res[0];
}
public int getHeight(Node head,int level, boolean[] res){
	if(head==null){
		return level;
	}
	int lH = getHeight(head.left,level+1,res);
	if(!res[0]){
		return level;
	}
	int rH = getHeight(head.right,level+1,res);
	if(!res[0]){
		return level;
	}
	if(Math.abs(lH-rH)>1){
		res[0]=false;
	}
	return Math.max(lH,rH);
}
 
//判断二叉树是否为完全二叉树
public boolean isCBT(Node head){
	if(head==null){
		return true;
	}
	Queue<Node> queue = new LinkedList<Node>();
	boolean leaf = false;
	Node l =null;
	Node r =null;
	queue.offer(head);
	while(!queue.isEmpty()){
		head = queue.poll();
		l = head.left;
		r = head.right;
		if((l==null&&r!=null)||(leaf&&(l!=null||r!=null))){
			return false;
		}
		if(l!=null){
			queue.offer(l);
		}
		if(r!=null){
			queue.offer(r);
		}
		else{
			leaf=true;
		}
	}
	return true;
}

//通过有序数组生成平衡搜索二叉树
public Node generateTree(int[] sortArr){
	if(sortArr==null){
		return null;
	}
	return generate(sortArr,0,sortArr.length-1);
}
public Node generate(int[] sortArr,int start,int end){
	if(start>end){
		return null;
	}
	int mid =(start-end)/2;
	Node head = new Node(sortArr[mid]);
	head.left = generate(sortArr,start,mid-1);
	head.right = generate(sortArr,mid+1,end);
	return head;
}

//找到两个节点的最近公共祖先
public Node lowestAncestor(Node head,Node o1,Node o2){
	if(head==null||head==o1||head==o2){
		return head;
	}
	Node left = lowestAncestor(head.left,o1,o2);
	Node right = lowestAncestor(head.right,o1,o2);
	if(left!=null &&right!=null){
		return head;
	}
	return left !=null?left:right;
}

//求二叉树节点间的最大距离
public int maxDistance(Node head){
	int[] record =new int[1];
	return posOrder(head,record);
}
public int posOrder(Node head,int[] record){
	if(head==null){
		record[0] = 0;
		return 0;
	}
	int lMax = posOrder(head.left,record);
	int maxfromleft = record[0];
	int rMax = posOrder(head.right,record);
	int maxfromright = record[0];
	int curNodeMax = maxfromleft+maxfromright+1;
	record[0] = Math.max(maxfromleft,maxfromright)+1;
	return Math.max(Math.max(lMax,rMax),curNodeMax);
}

//求二叉树第K层的节点个数
public int getLevelSize(Node head, int k){
	if(k<1){
		return 0;
	}
	int count = 0;
	if(head==null){
		return 0;
	}
	if(k==1){
		count++;
	}else{
		count = getLevelSize(head.left,k-1)+getLevelSize(head.right,k-1);
	}
	return count;
}

//Morris遍历二叉树
public void moriisIn(Node head){
	if(head==null){
		return;
	}
	Node cur1=head;
	Node cur2=null;
	if(cur1!=null){
		cur2=cur1.left;
		if(cur2!=null){
			while(cur2.right!=null&&cur2.right!=cur1){
				cur2 = cur2.right;
			}
			if(cur2.right==null){
				cur2.right = cur1;
				cur1 = cur1.left;
				continue;
			}else{
				cur2.right=null;
			}
		}
		System.out.print(cur1.value+" ");
		cur1 = cur1.right;
	}
}








 
 
 
 
 
 
 
 